[Day11] Advent of Code Day10 與 Racing the beam

2023 iThome 鐵人賽

DAY 11

自我挑戰組

從電子元件到傅立葉轉換 - 那些我有興趣的主題系列第 11 篇

15th鐵人賽

愷開

2023-09-22 20:25:14

174 瀏覽

分享至

（改寫自部落格文章）

2022 年的 Advent of Code 的 Day10 題目，剛開始題目是要求你實作一個超級簡易的 CPU，有一個暫存器以及兩個簡易的指令；第二部分是比較有趣的地方，暫存器實際上是 Sprite 的位置，然後 cycle 數則是目前的螢幕畫到哪裡。

Part1

題目的第一部分比較單調，是要實作一個只能跑兩個指令的 CPU（noop 跟 addx），這個 CPU 有一個 X 暫存器，然後計算在特定 cycle 的暫存器的值。照著指令的說明並根據 input 計算一下應該很快就有答案。題目描述當中其實有幾個和硬體有關的知識，雖然不影響解題，但我覺得很有趣，後面再來深入聊聊。

class CPU {
  x: number;
  cycles: number;

  constructor() {
    this.x = 1;
    this.cycles = 0;
  }

  tick() {
    this.cycles += 1;
  }

  noop() {
    this.tick();
  }

  addx(arg) {
    this.tick();
    this.tick();
    this.x += parseInt(arg);
  }
}

Part2

第二部分有趣很多，這個暫存器其實是 Sprite 的位置，然後 cycle 數則是目前的螢幕畫到哪裡。題目敘述當中有給出一個連結 – Racing the Beam。把程式碼加上螢幕繪圖的邏輯之後就可以了。

判斷是否繪製 # 的邏輯也可以用 bitwise 來做，例如用 0x111000 >> register 偏移後代表 sprite 的位置，再跟當前的 cycle 做 AND 就可以得到當前螢幕的字元。我這邊比較偷懶就直接一個一個比較了：

class CPU {
  // ...

  draw() {
    const column = this.cycles % 40;
    if (column === 0 && this.cycles !== 0) {
      this.screen += "\n";
    }

    if (this.x - 1 === column || this.x === column || this.x + 1 === column) {
      this.screen += "#";
      return "#";
    } else {
      this.screen += ".";
      return ".";
    }
  }
}

寫完之後我發現雖然將指令變成螢幕的圖像很簡單，但反過來困難很多。

也就是給你一個圖像後，生出對應的指令。為了達成這件事，要一邊算 cycle 數一邊移動下一個像素生成的位置，而且還不能太早或太晚。看了一下 Redit 上面的討論，發現有人也有同樣的想法，他用 Python 寫出了傳入 ASCII 圖片進去後會生出對應的指令。

Atari 2600

像是題目裡提到的 Atari2600，早期的遊戲機沒有額外的 video frame buffer 可以用，CPU 的記憶體又太小（只有 128KB）完全不夠用來畫滿整個螢幕，所以要盡可能重用記憶體（RAM）。

像這種需要繪圖計算的程式當中，通常會使用 frame buffer 來分擔 CPU 的工作，CPU 只要把對應位置的像素丟進去 frame buffer，GPU 會去處理剩下的事情，例如在正確的時間點繪製或是編碼、解碼成對應的輸出格式。然而沒有 frame buffer 輔助的情況下，圖片必須即時運算，而工程師只能把資料在有限的記憶體裡頭移來移去。

問題在於 CPU 跑指令也要時間（週期），如果記憶體移動太晚或太早都會導致掉幀，所以必須在正確的時間點移動記憶體。這就好像在跟 CRT 的電子光束賽跑一樣，因此才有了 Racing the Beam 這個名稱。

理解到諸多限制之後再回頭看看在 Atari 上面的小精靈（Pac-Man），我覺得能在記憶體少得可憐、CPU 慢得要命的情況下寫出遊戲真是奇蹟。還好我不是那個年代的工程師，不然應該會失業。

看了一下維基百科，Atari 2600 是使用 MOS 6507 開發的，根據維基上的描述是 MOS Technology 為了 Atari 遊戲機的開發而特別改良的，比 6502 便宜一倍。

兩年前看完任天堂的故事好奇之下買了 MOS 6502，但 6502 沒有內建 ROM，而且據我理解 6502 要用 Parallel ROM 才能夠讀取資料，但現在幾乎只能買到 Serial EEPROM，所以想要玩玩 6502 的計畫就一直擱著，看完這段故事後又有點動力了。（但還是不知道要去哪裡買 Parallel EEPROM）

Clock Circuit

為了讓 CPU 正常運作，通常需要透過振盪器來產生固定頻率。不過為什麼要這個振盪器呢？在玩完 Turing Complete 之後我才算是真正理解這件事。

在 CPU 裡有很多電路，有些電路很單純，像是加法器、邏輯閘等等，輸出完全取決於當下的輸入，在數位邏輯裡用 Combinatorial 來表示這樣的電路。

還有另外一種電路是具有記憶性的，像是暫存器，背後的原理是利用 flip-flops 電路組成。這類型的電路具有記憶性，輸出不只根據輸入，還會根據當前的狀態來決定。在數位邏輯裡用 Sequencial 來表示這樣的電路。具有記憶性這件事聽起來理所當然，但它是達成圖靈完備的必要條件之一。

回到為什麼要振盪器這件事情，主要是為了確保上述提到的狀態變化都發生在同一個時間點，而要達成這件事就需要有一個統一的時脈來源。舉例來說好了，假設我想要執行一個指令，將暫存器 r1 跟暫存器 r2 的值相加後儲存到暫存器 r1。

add r1, r2

在實際電路當中，r1 的值跟 r2 的值會同時取出後送到加法電路，得到結果後寫入 r1，而不是順序地執行：

取出 r1 的值
取出 r2 的值
送入加法電路
得到結果並寫入 r1

為了確保加法電路拿到的輸入正確，透過統一的時脈觸發信號，才能確保暫存器的變化是一致的。

不過這邊也要稍微強調一下，除了低功耗或是用在嵌入式的 CPU 以外，現代的 CPU（包含 Intel 跟 AMD）的架構超級複雜，為了最大化 CPU 效能做了很多神奇的事，不像前面講得那麼單純。例如：

Instruction Pipeline：CPU 執行指令可以分為 Fetch、Decode、Execution、Write Back 四大階段，在某些條件下我們可以在還沒 write back 之前就開始下一條指令的 fetch。
Out of order execution：一段指令可以被 CPU 按照電路狀態亂數執行（不按照指令的順序）
分支預測（Branch Predictor）：有技巧地去猜一段指令會進入的分支。